import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class IndexMaxPQ<Key extends Comparable<Key>> implements Iterable<Integer> {

    private int maxN;
    private int n;
    private int[] pq;
    private int[] qp;
    private Key[] keys;
    
    public IndexMaxPQ(int maxN) {
        if(maxN < 0) throw new  IllegalArgumentException();
        this.maxN = maxN;
        n = 0;
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];

        for(int i = 0; i <= maxN; i++) 
            qp[i] = -1;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public boolean contains(int i) {
        validateIndex(i);
        return qp[i] != -1;
    }

    public int size() {
        return n;
    }

    public void insert(int i, Key key) {
        validateIndex(i);
        if(contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
        n++;
        pq[n] = i;
        qp[i] = n;
        keys[i] = key;
        swim(n);
    }

    public int maxIndex() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    public Key maxKey() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow");
        return keys[pq[1]];
    }

    public int delMax() {
        if(n == 0) throw new NoSuchElementException("Priority queue underflow");
        int max = pq[1];

        exch(1, n--);
        sink(1);

        assert pq[n+1] == max;
        qp[max] = -1;
        keys[max] = null;
        pq[n+1] = -1;

        return max;
    }

    public Key keyOf(int i) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        else return keys[i];
    }

    public void changeKey(int i, Key key) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");

        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

    @Deprecated
    public void change(int i, Key key) {
        validateIndex(i);
        changeKey(i, key);
    }

    public void increaseKey(int i, Key key) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if(keys[i].compareTo(key) == 0)  
            throw new IllegalArgumentException("Calling decreaseKey() with a value equal to the" +
                "key in the priority queue");
        else if(keys[i].compareTo(key) > 0)
            throw new IllegalArgumentException("Calling decreaseKey() with a value strictly" + 
                "less than the key in the priority queue");
        keys[i] = key;
        swim(qp[i]);
    }

    public void decreaseKey(int i, Key key) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if(keys[i].compareTo(key) == 0)  
            throw new IllegalArgumentException("Calling decreaseKey() with a value equal to the" +
                "key in the priority queue");
        else if(keys[i].compareTo(key) < 0)
            throw new IllegalArgumentException("Calling decreaseKey() with a value strictly" + 
                "greater than the key in the priority queue");
        keys[i] = key;
        sink(qp[i]);

    }

    public void delete(int i) {
        validateIndex(i);
        if(!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }

    private void validateIndex(int i) {
        if(i < 0) throw new IllegalArgumentException("index is negative: " + i);
        if(i >= maxN) throw new IllegalArgumentException("index >= capacity: " + i);
    }

    private boolean less(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
    }

    private void exch(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;

        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while( 2 * k <= n) {
            int j = 2 * k;
            if(j < n && less(j, j+1)) j++;
            if(!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    public Iterator<Integer> iterator() { return new HeapIterator();}

    private class HeapIterator implements Iterator<Integer> {
        private IndexMaxPQ<Key> copy;

        public HeapIterator() {
            copy = new IndexMaxPQ<Key>(pq.length);
            for(int i = 0; i <= size(); i++)
                copy.insert(pq[i], keys[pq[i]]);
        }
        public boolean hasNext() {return !copy.isEmpty();}
        public void remove() { throw new UnsupportedOperationException();}

        public Integer next() {
            if(!hasNext()) throw new NoSuchElementException();
            return copy.delMax();
        }
    }

    public static void main(String[] args) {

    }
}